package com.sunny.l19;

public class Solution {

    private static final int maxN = 1000;
    private int[][] dp = new int[maxN][maxN];

    public static void main(String[] args) {

        String s = "ab";
        System.out.println(new Solution().minCut(s));

    }

    public int minCut(String s) {

        int len = s.length();
        for(int i=1;i<=len;i++){
//            System.out.println("len="+i);
            for(int j=0;j+i-1<len;j++){
//                System.out.println("start="+j+";end="+(j+i-1));
                if(judgePalindrome(s.substring(j, j+i))){
                    dp[j][j+i-1] = 0;
                }else{
                    int tmpMin = Integer.MAX_VALUE;
                    for(int k=j;k<j+i-1;k++){
                        if(dp[j][k] + dp[k+1][j+i-1] + 1 < tmpMin){
                            tmpMin = dp[j][k] + dp[k+1][j+i-1] + 1;
                        }
                    }
                    dp[j][j+i-1] = tmpMin;
                }
//                System.out.println("this result = " + dp[j][j+i-1]);
            }
        }
        return dp[0][len-1];

    }

    public boolean judgePalindrome(String s){
        int i = 0;
        int j = s.length()-1;
        boolean flag = true;
        while (i < j){
            if(s.charAt(i) != s.charAt(j)){
                flag = false;
                break;
            }
            i++;
            j--;
        }
        return flag;
    }
}
